package com.heyqing.medium.day5;

import java.util.*;
import java.util.stream.Collectors;

/**
 * ClassName:RemainingMethods
 * Package:com.heyqing.medium.day5
 * Description:
 *
 * @Date:2024/10/6
 * @Author:Heyqing
 */
public class RemainingMethods {

    /**
     * 使用深度优先算法 DFS
     *
     * @param n
     * @param k
     * @param invocations
     * @return
     */
    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {

        List<Integer>[] doubt = new ArrayList[n];
        Arrays.setAll(doubt, i -> new ArrayList<>());
        for (int[] invocation : invocations) {
            doubt[invocation[0]].add(invocation[1]);
            System.out.println(invocation[0] + " " + doubt[invocation[0]]);
        }
        //标记所有可以方法
        boolean[] isDoubt = new boolean[n];
        dfs(k, doubt, isDoubt);
        //检查是否有非可疑方法依赖可疑方法
        for (int[] invocation : invocations) {
            if (!isDoubt[invocation[0]] && isDoubt[invocation[1]]) {
                List<Integer> result = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    result.add(i);
                }
                return result;
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!isDoubt[i]) result.add(i);
        }
        return result;
    }

    private void dfs(int k, List<Integer>[] doubt, boolean[] isDoubt) {
        isDoubt[k] = true;
        for (Integer d : doubt[k]) {
            if (!isDoubt[d]) dfs(d, doubt, isDoubt);
        }
    }

}
